package com.heima.algorithm.greedy;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 活动选择问题，指定时间内举行尽可能多的活动
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/1 10:08
 */
public class ActiveSelectionProblem {
    /*
    几种贪心策略：

    1、优先选择时间最短的活动

             1， 2， 3， 4， 5， 6， 7， 8， 9， 10  时间
          1  [--------------)
          2              [----------)
          3                     [---------------)
       活动编号

       很明显活动2并不是最优解，最优解应该是活动1，活动2

    2、优先选择最少冲突的活动
             1， 2， 3， 4， 5， 6， 7， 8， 9， 10， 11， 12， 13， 14 时间
          1  [-----------)                                                  3
          2         [-------)                                               4
          3         [-------)                                               4
          4         [-------)                                               4
          5              [------)                                           4
          6                 [-------)                                       2
          7                     [---------------)                           4
          8                                 [-------------)                 4
          9                                 [-------------)                 4
         10                                 [-------------)                 4
         11                                          [--------)             3
      活动编号                                                           冲突活动数

      得出的的活动组合是活动1、活动6、活动11，但是这依旧不是最优解：活动1、活动5、活动7、活动11

     3、选择最先开始的活动
                  1， 2， 3， 4， 5， 6， 7， 8， 9， 10  时间
          1  [---------------------------------------)
          2          [----------)
          3                     [---------------)
       活动编号

       由此可见活动1并不是最优解，最优解是活动2、活动3

     4、优先选择最先结束的活动，思想：尽可能快速释放资源，让别人来用，让局部最优解堆叠而成整体最优解
     上述几个例子可以依次试试

     */

    /**
     * 活动类
     */
    public static class Active{
        int index; // 活动编号
        String name; // 活动名称
        int start; // 活动开始时间，包含
        int end; // 活动结束时间，包含

        public Active(int index,String name, int start, int end) {
            this.index = index;
            this.name = name;
            this.start = start;
            this.end = end;
        }

        public int end() {
            return end;
        }

        public String name() {
            return name;
        }

        @Override
        public String toString() {
            return "Active{" +
                    "index=" + index +
                    ", name=" + name +
                    ", start=" + start +
                    ", end=" + end +
                    '}';
        }
    }

    /**
     * 选择活动
     * @param activeList 活动列表
     * @return 选择的活动
     */
    public List<Active> select(List<Active> activeList){
        PriorityQueue<Active> queue = new PriorityQueue<>(Comparator.comparingInt(Active::end));
        List<Active> result = new ArrayList<>();
        queue.addAll(activeList);
        result.add(queue.poll());
        while (!queue.isEmpty()){
            Active poll = queue.poll();
            if (poll.start > result.get(result.size() - 1).end){
                result.add(poll);
            }
        }
        return result;
    }
}
